package LC;

import sun.misc.LRUCache;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * @ClassName LC146
 * @Description: TODO
 * @Author hl
 * @Date 2020/10/8
 * @Version V1.0
 **/
public class LC146 {
    class Node{
        int value;
        int key;
        Node pre;
        Node next;
        public Node() {
        }
        public Node(int key, int value ) {
            this.value = value;
            this.key = key;
        }
    }
    int size;//大小
    int capacity;//容量
    Node head,tail;
    HashMap<Integer,Node> map=new HashMap<>();


    public LC146(int capacity) {
        this.size=0;
        this.capacity=capacity;
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }


    public int get(int key) {
        Node temp=map.get(key);
        if(temp==null) return -1;
        moveFirst(temp);
        return  temp.value;
    }



    public void put(int key, int value) {
       Node temp=map.get(key);
       if(temp!=null){
           temp.value=value;
           moveFirst(temp);
       }else{
        //addLast(new Node(key,value));
           Node newNode=new Node(key,value);
          map.put(key,newNode);
        addFirst(newNode);
        size++;
        if(size>capacity){
            map.remove(moveLast().key);
            size--;
        }
       }
    }

    private Node moveLast() {
       Node pre=tail.pre;
       move(pre);
       return pre;
    }

    private void moveFirst(Node temp) {
        move(temp);
        addFirst(temp);
    }

    private void addFirst(Node temp) {
        temp.pre=head;
        temp.next=head.next;
        head.next.pre=temp;
        head.next=temp;
    }



    private void move(Node temp) {
        temp.pre.next=temp.next;
        temp.next.pre=temp.pre;
    }
}
class Test{
    public static void main(String[] args) {
        LC146 cache = new LC146( 1 /* 缓存容量 */ );

        cache.put(2,1);
        System.out.println(cache.get(2));


    }
}
